<?php

namespace Coding\php;

include 'init.php';


class Algorithm
{
    public function run()
    {
        $arr = [13, 99, 14, 34, 56, 15, 23, 78, 999, 200];

        $list = $this->sortByFast($arr);

        $list = $this->sortByPop($arr, 'asc');

        $targetIndex = $this->binSearch($list, 78);
    }


    /**
     * 快速排序
     * 原理是利用递归, 分治的思想, 将数组按照某个中间值, 分别放入中间值左右两边, 
     * 然后依次递归, 最后合并数组, 变成排好顺序的数组, 
     * 遍历的时候, 不能在从数组的0下标开始了, 因为第0号元素已经当成中间值拿出来了
     */
    public function sortByFast(&$list, $sortBy = 'asc')
    {

        if (count($list) <= 1) {
            return $list;
        }

        $mv = $list[0];
        $left = [];
        $right = [];
        for ($i = 1, $cnt = count($list); $i < $cnt; $i++) {
            if ($list[$i] > $mv) { // 大于中间值的, 放在右侧
                $right[] = $list[$i];
            } else {
                $left[] = $list[$i];
            }
        }

        $left = $this->sortByFast($left);
        $right = $this->sortByFast($right);
        return array_merge($left, [$mv], $right);
    }

    /**
     * 冒泡排序, 两层循环嵌套 ,
     * 外循环: 遍历一次, 数组元素, 两两比较, 产出一个最大值, 移动到最右侧
     * 内循环: 负责亮亮比较, 如果左边比右边值大, 则交换两个值的位置
     * 如果比较条件是:
     *    1. 左数比右数大, 则最终产出的数组是升序排列
     *    2. 左数比右数小, 则最终产出的数组是降序排列
     */
    public function sortByPop($list, $sortBy = 'asc')
    {
        for ($i = 0, $cnt = count($list); $i < $cnt; $i++) {
            for ($j = 0, $jnt = ($cnt - $i - 1); $j < $jnt; $j++) {
                if ($sortBy == 'asc') {
                    if ($list[$j] > $list[$j + 1]) {
                        $temp = $list[$j];
                        $list[$j] = $list[$j + 1];
                        $list[$j + 1] = $temp;
                    }
                } else { // desc 排列
                    if ($list[$j] < $list[$j + 1]) {
                        $temp = $list[$j];
                        $list[$j] = $list[$j + 1];
                        $list[$j + 1] = $temp;
                    }
                }
            }
        }
        return $list;
    }

    /**
     * 二分法, 找到指定的一个数值
     * 对数组有要求, 必须是已经按照顺序排列好的, 对于数组的排列顺序没有要求, 
     * 但是如果是倒序排列的, 意味着当目标值小于中间值则说明目标值在中间值的右侧, 则left/right的位移关系就要反过来
     * 
     * 原理是: 
     *       数组最左边索引记为left, 最右边索引记为right;
     *       while循环只在left <= right 时才成立
     *       先将数组劈成两半, 找到中间索引$m
     *       如果目标值小于中间值, 则说明目标值在中间值左侧, 则将数组最右边索引重置为 right = m -1 , 理解为m的位置, 向左偏了一位
     *       如果目标值大于中间值, 则说明目标值在中间值右侧, 则将数组最左边索引重置为 left = m+1 , 理解为m的位置, 向右偏了一位     * 
     *       如果目标值==中间值, 则说明目标值等于中间值, 理解为找到了目标值, 此时中间索引$m就是目标值的索引
     *       如果 left > right时, 代表目标值, 不在这个数组内, 理解不存在, 没找到
     */
    public function binSearch($list, $target)
    {
        $left = 0;
        $right = count($list) - 1;
        while ($left <= $right) {
            $m = floor(($right + $left) / 2);

            echo sprintf("left: %s, right: %s, m: %s \n", $left, $right, $m);
            if ($list[$m] == $target) {
                console_log("找到了target, 索引为: " . $m);
                return $m;
                break;
            } else if ($list[$m] > $target) {
                $right = $m - 1;
            } else {
                $left = $m + 1;
            }
        }
        return -1;
    }



    /**
     * 这个是没翻答案之前自己写的简陋版二分查找, 
     * 能找到, 但是有点小问题, 无法判断当前值是否在数组内
     * 
     */
    public function binSearchOld()
    {
        $arr_raw = [13, 14, 15, 23, 34, 56, 78, 99, 200, 999];
        $arr = [13, 14, 15, 23, 34, 56, 78, 99, 200, 999];
        // $arr  0   1   2   3   4   5   6   7   8    9

        $min = $arr_raw[0];
        $max = end($arr_raw);
        $cnt = count($arr);
        $target = 203;
        $times = 0;
        while (true) {
            if ($target < $min || $target > $max) {
                exit('target超出数组范围');
            }
            for ($i = 0; $i < $cnt; $i++) {
                $m = floor($cnt / 2);
                if ($i > 0) {
                    $m = floor(($cnt - $i + 1) / 2);
                    $m = $i + $m - 1;
                }
                $mv = $arr_raw[$m];
                // todo 如何判断值不存在于数组中
                $times += 1;
                echo sprintf("i:%s, cnt:%s, m:%s, mv:%s \n", $i, $cnt, $m, $mv);
                if ($target > $mv) {
                    $i = $m;
                    continue;
                } else if ($target == $mv) {
                    exit(sprintf("遍历%s次, 找到目标键%s, 值:%s", $times, $m, $target));
                } else { // 目标小于中间值
                    $cnt = $m;
                    break;
                }
            }
        }
    }
}


$algorithm = new Algorithm();

$algorithm->run();
